use std::collections::LinkedList;
use std::rc::Rc;

struct TreeNode {
    info: String,
    left: Option<Rc<TreeNode>>,
    right: Option<Rc<TreeNode>>
}

#[derive(Clone)]
struct PushRef {
    node: Option<Rc<TreeNode>>,
    pushed: bool
}

impl TreeNode {
    pub fn leaf(info: &str) -> Option<Rc<TreeNode>> {
        Option::from(Rc::new(
            TreeNode {
                info: String::from(info),
                left: Option::None,
                right: Option::None
            }
        ))
    }

    pub fn trunk( 
        left: Option<Rc<TreeNode>>, 
        right: Option<Rc<TreeNode>>,
        info: &str) -> Option<Rc<TreeNode>> {
            Option::from(Rc::new(
                TreeNode {
                    info: String::from(info),
                    left: left,
                    right: right
                }
            ))
    }
}

fn init_tree() -> Option<Rc<TreeNode>> {
    println!("tree diagam:");
    println!("   A");
    println!("  / \\");
    println!(" B   C");
    println!("/ \\ / \\");
    println!("D E F G");

    let left = TreeNode::trunk(
        TreeNode::leaf("D"),
        TreeNode::leaf("E"),
        "B"
    );
    
    let right = TreeNode::trunk(
        TreeNode::leaf("F"),
        TreeNode::leaf("G"),
        "C"
    );
    
    TreeNode::trunk(
        left, 
        right, 
        "A"
    )
}

fn nlr_trav(tree: &Option<Rc<TreeNode>>, cb: fn(&String)) {
    let mut node_stack: LinkedList<Rc<TreeNode>> = LinkedList::new();

    node_stack.push_front(tree.clone().unwrap());
    while node_stack.len() > 0 {
        let cur = node_stack.pop_front().unwrap();

        cb(&cur.info);
        if let Some(child) = &cur.right {
            node_stack.push_front(child.clone());
        }
        
        if let Some(child) = &cur.left {
            node_stack.push_front(child.clone());
        }
    }
}

fn lnr_trav(tree: &Option<Rc<TreeNode>>, cb: fn(&String)) {
    let mut node_stack: LinkedList<Option<Rc<TreeNode>>> = LinkedList::new();

    let mut cur = tree.clone();
    while node_stack.len() > 0 || cur.is_some() {
        if let Some(ref node) = cur {
            node_stack.push_front(cur.clone());
            cur = node.left.clone();
        } else {
            cur = node_stack.pop_front().unwrap();
            
            if let Some(ref next) = cur {
                cb(&next.info);
                cur = next.right.clone();
            }
        }
    }
}

fn lrn_trav(tree: &Option<Rc<TreeNode>>, cb: fn(&String)) {
    let mut node_stack: LinkedList<PushRef> = LinkedList::new();

    let mut cur = PushRef {
        node: tree.clone(),
        pushed: false
    };

    while node_stack.len() > 0 || cur.node.is_some() {
        if let Some(ref node) = cur.node {
            node_stack.push_front(cur.clone());
            cur = PushRef {
                node: node.left.clone(),
                pushed: false
            };
        } else {
            cur = node_stack.pop_front().unwrap();
            
            if !cur.pushed {
                cur.pushed = true;
                node_stack.push_front(cur.clone());

                cur = PushRef {
                    node: cur.node.as_ref().unwrap().right.clone(),
                    pushed: false
                }
            } else {
                cb(&cur.node.as_ref().unwrap().info);
                
                cur = PushRef {
                    node: Option::None,
                    pushed: false
                }
            }
        }
    }
}

fn main() {
    let cur: Option<Rc<TreeNode>> = init_tree();

    let print_node = |x: &String| { 
        println!("{}", x);
    };

    println!("NLR traverse: ");
    nlr_trav(&cur, print_node);
    println!("LNR traverse: ");
    lnr_trav(&cur, print_node);
    println!("LRN traverse: ");
    lrn_trav(&cur, print_node);
}
